Ad-hoc wireless networks are networks that are formed and de-formed on-the-fly without the need for system administration. Ad-hoc networks can be mobile, standalone, or networked with other networks such as wide area networks or the Internet. Ad-hoc wireless devices communicating in a wireless area network are able to detect the presence of other ad-hoc devices, establish communication links with the other devices, and communicate information such as packetized digital data. An ad-hoc network is essentially infrastructureless since there is no need for fixed radio base station, wires, or routers in the network. In communicating with each other, ad-hoc devices may employ many different packet routing methods to route wireless digital packets between mobile hosts in an ad-hoc mobile network.
One wireless networking protocol of significant importance due in part to its growing use in devices such as palmtop computers, personal digital assistants (PDAs), laptop computers, and Internet mobile phones is IEEE 802.11. The 802.11 standard specifies two modes of operation: an infrastructure mode where an access point provides the link between wireless stations and wireline legacy infrastructure, and an ad-hoc mode where there is no access point, and wherein all stations contribute to the distributed management and control of the network.
802.11 equipped devices configured to run in infrastructure mode are especially well suited for office, home, or café environments where there is an access point, and where the concentration of mobile devices is relatively low and the mobile devices are slow moving or stationary. For example, in a café or office setting a mobile device such as a laptop computer may enter a wireless network and remain stationary for a long period of time while the user of the device accesses other devices or other networks, such as the Internet. Location and context based mobile services are another infrastructure mode application. For example, a user in a shopping mall could obtain the lowest price for a product they are interested in. Or, a user at an art museum could automatically receive on their PDA more detailed information on a work of art as they approach to view the work of art.
Mobile ad-hoc devices can automatically recognize the presence of and communicate with other compatible ad-hoc wireless devices. For example, when two or more people meet at conference they may form an ad-hoc network to exchange data between their wireless ad-hoc mode enabled PDAs or laptop computers. In another application, a user's ad-hoc device communicates with home wireless devices to unlock doors, activate lights and home audio and video equipment units, adjust heating and cooling settings, and the like. These applications are similar in that the network is formed spontaneously, and the mobile device need only communicate small amounts of data in order to carry out the application.
Still another mobile ad-hoc application is car-to-car mobile communications whereby ad-hoc mobile communication devices in cars will allow the formation and de-formation of ad-hoc wireless networks with other cars. These networks could be used to send alert messages to motor vehicle operators, including alerts to traffic accidents, traffic congestion, weather reports, emergency vehicles en-route, and the like.
Unlike the other examples above, car-to-car mobile communications present significantly greater challenges since, at the very least, the communication devices present in the vehicles are moving extremely fast relative to each other. For example, while some vehicles may be traveling on a highway in the same direction within close proximity to each other, others are moving in opposite direction. If the vehicles are traveling 60 mph, the mobile devices may be traveling 120 mph relative to each other. This, in addition to the relatively limited range of 802.11, presents only a very small communication window within which to set up communication links, and transmit and receive information in a reliable fashion. Typically, the range for outdoor communication using 802.11 is between 0.5 and 1 mile. In above example, for vehicles moving in opposite directions, this translates to a communication window of between 10 and 30 seconds. Additionally, due to the small window, it may only be possible to transmit a very small amount of data before the devices are out of range of each other. Further, in a transportation network with many vehicles equipped with 802.11 devices, or radios, there may be hundreds or thousands of radios within range of each other at any particular moment in time. Current ad-hoc mobile protocols are generally not suitable for coping with such a high concentration of radios, in addition to the extremely short windows with which to set up links and transmit data.
One of the more popular devices found in automobiles today are Global Positioning System (GPS) navigation devices. Several manufacturers offer GPS navigation devices that provide varying degrees of information from basic position as indicated by latitude and longitude, speed, and direction, to detailed driving directions to a destination. For example, the Garmin StreetPilot III provides real-time location information overlaid onto a map. Exemplary devices such as the StreetPilot III also provide real-time driving directions en-route to a destination through audible or visual commands emanating from the device.
Typically, navigation devices include an interface port, such as a serial or universal serial bus (USB) port, for interfacing to an external computing or storage device such as a laptop computer. Additionally, devices may also include a non-volatile storage medium, such as a removable flash memory card. The port and memory card are used to download maps and planned routes onto the device. Maps such as city and interstate road maps, topographical maps, recreational maps, and the like are stored on removable storage such as a CD-ROM disc. Based on the limitations or the GPS navigation device and the user's preference and requirements, some or all of the map data on the CD-ROMs can be placed on the GPS navigation device through either the interface port, or by placing the desired map data on a flash memory card and inserting the card into the GPS navigation device. Additionally, a laptop computer or other computing device can be used in conjunction with the maps to plan routes, taking into account variables such as desired areas of interest and preferred roads. Once the routes are planned the trip data is downloaded to the GPS navigation device in the manner specified above.
When used in a motor vehicle and loaded with the appropriate map data, a GPS navigation device such as the StreetPilot III can provide real-time driving instructions to the motor vehicle operator en-route to a destination. Typically, at the outset of the trip or while in transit, the motor vehicle operator enters the desired destination, or chooses from among the preplanned routes that were downloaded to the device. The GPS navigation device periodically checks the position of the motor vehicle through the use of GPS sensors located in the device or vehicle. The position is correlated with positions on the downloaded map and real-time driving directions are relayed to the motor-vehicle operator. In the event the motor vehicle deviates from the planned path, the GPS navigation device can recompute a new path to the destination based on the current position of the vehicle and the available routes as indicated on the map.
There are many ways to compute a route to a destination. The most common method falls under the category of distance based shortest path routing. In distance based shortest path routing, a route is selected based on an algorithm that uses absolute distance as a comparison metric. This path may not be the fastest path however. Since speed limits vary from path to path, it may take more time for a vehicle to reach its destination depending on the path taken. To provide a better overall route choice, some advanced geographic information system (GIS) databases, or maps, comprise information such as speed limits. This additional information can be used in conjunction with absolute distance to select the shortest route to the destination based on the overall estimated delay.
The GPS navigation devices described above have no way to take into account current traffic conditions such as congestion, closed roads, accidents, and the like, in planning routes. Thus, while an uncongested alternate route might be available en-route to a destination, it is likely that the GPS navigation device will plan a route and issue instruction that take the motor vehicle into the heart of a traffic jam merely because that route appears to be the shortest or fastest on a map. In order to try to avoid areas of congestion and thus minimize drive time, the motor vehicle operator must rely on radio reports, which may be incomplete or delayed in time, or rely on an intuitive feel for traffic patterns given the area and time of day of travel, and adjust their route accordingly. Often by the time the motor vehicle operator has realized that they are going to hit a pocket of traffic congestion or other undesirable traffic condition, it is too late to take an alternate route and the motor vehicle and its occupants must simply sit in the traffic, wasting valuable travel time, as well as fuel.
Various systems have been devised to communicate traffic conditions to motor vehicle operators in order to better avoid the involved regions or roads and plan the trip accordingly. All of these systems however rely at least in part on external communication networks, in addition to radio news reports, central databases, roadside sensors, and environmental sensors to sense and share traffic information. One standard for roadside to vehicle communications is IEEE 1455. U.S. Pat. No. 6,252,544 describes a mobile communication device for outputting environmental statuses, such as inclement weather, traffic jams, construction, radar traps, and the like to motor vehicle operators. The mobile communication device makes use, at least in part, of various vehicle sensors radar detectors, safety warning systems, optical systems, roadside communication systems, remote databases, and the like to transmit and receive environmental events and notify the motor vehicle operator of those events in advance. Another system described in U.S. Pat. No. 5,732,383 describes a method to estimate traffic conditions based on cell phone use activity. These and other systems have the disadvantage of requiring external traffic reporting systems and a variety of sensors and communication systems to accurately report conditions.
U.S. Pat. No. 6,101,443 describes a system to compute a detour route in response to road traffic information. This system also relies on an external road traffic information reporting system. Other systems such as U.S. Pat. No. 5,610,821 attempt to assign routes to vehicles to maintain optimal traffic system stability. But these systems depend upon, at least in part, roadside antennas and centralized databases and computers to globally compute routes for all the vehicles in the network. U.S. Pat. No. 4,350,970 also describes a method for traffic management comprising a routing and information system for motor vehicle traffic that uses stationary routing stations each located in the vicinity of the roadway which transmit route information.
Thus, a need presently exists for an enhanced mobile communication device capable of operating in fast moving and high density networks such as a motor vehicle transportation network. Further, a need presently exists for an enhanced vehicle navigation system and transportation network that can communicate traffic conditions and traffic congestion information among the vehicles in the transportation network without the need for external antennas, external radios, and other roadside and centralized devices of the prior art. A need also exits for a system and method for analyzing traffic congestion information and plan routes through a transportation network.